Computer systems have traditionally been used for the storage and retrieval of data. Data is the raw stuff that makes up information. Data is comprised of bits and bytes stored on computer readable medium. Aside from these definitions, data can be defined in any manner suitable for a particular application. Information is generally thought of as useful stuff that is represented by data. For example, a report on stock price history is, according to this definition, information. The actual stock prices for one or more time periods are generally considered to be the raw data that makes up the information. Again, these definitions are presented here only to illustrate some basic concepts. In fact, the actual definition of these terms has been, and will doubtlessly continue to be widely debated.
Whatever the definitional precepts used to refer to data or information, one common objective remains that of efficient storage, retrieval and management of data (and/or information). Storage, retrieval and management of information are accomplished through the use of programmatic algorithms that manipulate data structures. Today, these are executed and maintained on computing systems.
A data structure is a mechanism for collecting related data. For example, related data can include a stock opening price and a stock closing price on a particular stock trading day. Another example of related data can include an inventory stock item number, a description of the item and an inventory quantity value. These examples are presented here to further illustrate some basic concepts and are not intended to limit the application of other concepts introduced in the detailed description that follows.
A commonly used data structure is known as a linked-list. A linked-list comprises a collection of one or more a data elements. Typically, each of these data elements includes at least one data container and at least one reference to another data element. Generally, a referenced element is the next element in a chain of elements; hence the term linked-list. It should be noted that the term “data element” (or simply “element”), as used herein, refers to a single data structure of a particular definition. A linked-list, for example, will include one or more such elements.
A linked-list is commonly used to hold data (or information depending on your perspective). Once the data is stored in the linked list, it is a fairly simple task to “traverse” the linked-list in order to discover needed data. In one common application of a linked-list, data is first retrieved from a slower computer readable medium, for example a hard disk drive or a compact disk (CD) read-only-memory (ROM). Once the data is retrieved from the slower computer readable medium, it is stored in the linked-list from whence it can be quickly retrieved.
One problem with a linked-list is that this type of data structure does not readily accommodate access by multiple processes. For example, consider a situation where a linked-list is used to store data pertaining to the inventory of a retail store. If multiple point-of-sale terminals need to access or modify the linked-list, there may be significant delay. This is because of the very nature of a linked list. In order to use a linked-list, the list must remain constant during a particular access session. Because each element in the linked-list is referenced by a preceding element, a process that needs to search for data stored in some arbitrary element in the linked-list needs to examine the contents of each element. Examination of each element is needed to determine if that element has the requisite data to fulfill a process search. Accordingly, once the data has been discovered, further examination is moot except in the case where a thorough and complete search of the linked-list is required. Examination of each element is also required to discover the next element in the linked-list by way of a reference included in a current linked-list element.
This becomes extremely problematic in a multi-processor environment. Especially when considering the need to discover a subsequent element in a linked-list by means of a reference included in its predecessor. When one process needs to search for data in the linked-list, all other processes must be staved-off so that the linked-list is not altered. If a first process were to relinquish control over a linked-list during a search, a second process may inadvertently (or more probably, deliberately, but with no malice) remove an element or add an element to the linked-list. Either of these two functions would corrupt the reference chain that the first process needs to complete a search activity. Because of this, a process can not relinquish control of a linked-list during a search. This renders the linked-list a resource subject to periods of unavailability when one process is using the list. Other processes that need to gain access to the list are forced to wait for the completion of any pending data search.